#include <bits/stdc++.h>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void printf_list(ListNode *head)
{
    ListNode *cur = head;
    while (cur != nullptr)
    {
        printf("%d ", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

class Solution
{
public:
    // ListNode *detectCycle(ListNode *head)
    // {
    //     ListNode *cur = head;
    //     map<ListNode *, bool> flag;
    //     while (cur != nullptr)
    //     {
    //         if (flag.find(cur) != flag.end())
    //         {
    //             return cur;
    //         }
    //         else
    //         {
    //             flag.insert(pair<ListNode *, bool>(cur, true));
    //         }
    //         cur = cur->next;
    //     }
    //     return nullptr;
    // }

    ListNode *detectCycle(ListNode *head)
    {
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
            {
                ListNode *index1 = head;
                ListNode *index2 = fast;
                while (index1 != index2)
                {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return nullptr;
    }
};

int main()
{
    ListNode *head = new ListNode(3);
    ListNode *node1 = new ListNode(2);
    ListNode *node2 = new ListNode(0);
    ListNode *node3 = new ListNode(-4);

    head->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = node1;

    Solution sol;
    ListNode *cycle_node = sol.detectCycle(head);

    cout << cycle_node->val << endl;

    return 0;
}
